
function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

/**
 * @param {string} traversal
 * @return {TreeNode}
 */
var recoverFromPreorder = function(traversal) {
  let arr = [], char = 0, num = '';
  for(let i = 0; i < traversal.length; i++) {
    if(traversal[i] == '-') {
      if(num) {
        let node = new TreeNode(parseInt(num));
        arr.push({
          node,
          level: char
        });
        num = '';
        char = 0;
      }
      char++;
    }
    else {
      num += traversal[i];
    }
  }
  let node = new TreeNode(parseInt(num));
  arr.push({
    node,
    level: char
  });

  function preorderCreateTree(array) {
    // console.log("array", array);
    if(array.length == 0)
      return null;
    if(array.length == 1)
      return array[0].node;
    let root = array[0].node, childLevel = array[1].level, rightIndex = -1;
    for(let i = 2; i < array.length; i++) {
      if(array[i].level === childLevel) {
        rightIndex = i;
        break;
      }
    }
    if(rightIndex == -1) {
      root.left = preorderCreateTree(array.slice(1, array.length));
      root.right = preorderCreateTree([]);
    } else {
      root.left = preorderCreateTree(array.slice(1, rightIndex));
      root.right = preorderCreateTree(array.slice(rightIndex, array.length));
    }
    return root;
  }

  return preorderCreateTree(arr);
};
let str = "1-2--3--4-5--6--7";
console.log(recoverFromPreorder(str));
str = "1-2--3---4-5--6---7";
console.log(recoverFromPreorder(str));
str = "1-401--349---90--88";
console.log(recoverFromPreorder(str));
